function quickSort(arr: number[]): number[] {
  //input your code here
  // let left: number = 0;
  // let right: number = arr.length - 1
  // if (left < right) {
  //   let i: number = left
  //   let j: number = right
  //   let x = arr[left]
  //   while(i < j) {
  //     while(i < j && arr[j] >= x)  // 从右向左找第一个小于x的数
  //     j--;
  //     if (i < j) {
  //       arr[i++] = arr[j]
  //     }
  //     while(i < j && arr[i] < x)   // 从左向右找第一个大于等于x的数
  //     i++
  //     if (i < j) {
  //       arr[j--] = arr[i]
  //     }
  //   }
  //   arr[i] = x
  //   quickSort(arr, l, i - 1); // 递归调用 
  //   quickSort(arr, i + 1, r);
  // } 
  // return arr
  // let index = Math.floor(arr.length / 2)
  // while(index > 0) {
  //   for (let i = 0; i < arr.length; i++) {
  //     let n = i
  //     while(arr[n] < arr[n - index] && n > 0) {
  //       let temp = arr[n]
  //       arr[n] = arr[n - index]
  //       arr[n - index] = temp
  //       n = n - index
  //     }
  //   }
  //   index = Math.floor(arr.length / 2)
  // }
  // return arr
  // if (arr.length <= 1) { return arr }
  // // 取基准值
  // var index = Math.floor(arr.length / 2);      // 基准值的索引
	// var pivot = arr.splice(index, 1)[0];         // 将基准值赋给变量 pivot 并从数组中将其删除
	// var left: any = [];		// 存放基准值左边的数据
	// var right: any = [];		// 存放基准值右边的数据
  // for (var i = 0; i < arr.length; i++) {
  //   if (arr[i] < pivot) {
  //     left.push(arr[i]);	   // 小于基准值存入 left 中
  //   } else {
  //     right.push(arr[i]);	// 大于基准值存入 right 中
  //   }
  // }

  // return quickSort(left).concat([pivot], quickSort(right));	// 递归调用
  if (arr.length <= 1) return arr
  // 选择第 0 个作为基准，定义两个数组
  var pivot = arr[0]
  var left: any = []
  var right: any = []
  // 删除基准值
  arr.shift()
  // 数值分类
  arr.forEach(item => {
    item < pivot ? left.push(item) : right.push(item)
  })
  return quickSort(left).concat([pivot], quickSort(right))
}

function generateCases(length: number, step: number = 1): number[] {
  const a: number[] = []
  let value = 0
  for (let i = 0; i < length; i++) {
      a.push(value)
      value += step
  }
  let tmp: number
  for (let i = 0; i < length; i++) {
      const f = Math.random() * (length - i)
      const r = i + Math.floor(f)
      tmp = a[r]
      a[r] = a[i]
      a[i] = tmp
  }
  return a
}

function checkRes(arr: number[], step: number): boolean {
  for (let i = 0; i < arr.length - 1; ++i) {
      if (arr[i] + step !== arr[i+1]) return false
  }
  return true
}


function testQuickSort() {
  for (let i = 6; i <= 100000; i = i * 2) {
      const randomStep = Math.ceil(Math.random() * 10)
      const arr = generateCases(i, randomStep)
      const start = Date.now()
      const ret = quickSort(arr)
      const end = Date.now()
      console.log(`Quick sort for ${i} numbers costs ${end - start}ms`)
      if (!checkRes(ret, randomStep)){
          console.log(`Fail`)
          return false
      } else {
          console.log("Passed")
      }
  }
  return true
}

testQuickSort()
//quickSort([ 60, 66, 90, 30, 96, 42, 6, 84, 0, 24, 18, 54, 48, 78, 102, 36, 72, 12 ])
